
Khan S. Alam 17 https://E-next.in
Algorithm:
1. Declare necessary variables such as n, A, B, C etc.
2. Input number of disks
3. If n=1
move single disk from peg A to peg C and stop.
Else
move the top (n-1) disks from peg A to peg B using peg C as auxiliary.
4. Move remaining disks from peg A to peg C.
5. Move (n-1) disks from peg B to peg C using peg A as auxiliary
Q xii)Theoretically explain the eight-queen problem
Ans:
A classic chess problem requires that you place eight queens on the chess board in such a way
that no queen can capture another queen. The eight queens puzzle is the problem of placing
eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution
requires that no two queens share the same row, column, or diagonal.
The computer solution to this problem requires that we place a queen on the board and then
analyze all of the attack positions to see if there is a queen that could capture the new queen. If there
is, then we try another position.
The queen’s capture rules and one solution are shown below:
Four Queens Solution
This problem can be solved using a stack and backtracking logic, because only one queen can
be placed in any row. So we begin by placing one queen in row 1, column 1 and this position is pushed
into the stack. (Step–1)
After placing a queen in the first row, look for a position in the second row. Position 2,1 is not
possible because the queen in the first row is guarding this location on the vertical. Likewise, 2,2 is
guarded on the diagonal. Therefore we place a queen in the third column in row 2 and push this
location into the stack (Step-2)
Now try to locate a position in row 3, such that no other queen can capture another queen but
none are possible. The first column is guarded by the queen in row 1 and the other three positions are
guarded by the queen in row 2. At this point we must backtrack to the second row by popping the
stack and continue looking for a position for the second-row queen, because column 4 is not guarded,
we place a queen there and push its location into the stack. (Step-3)
Now, again at row 3, we see that the first column is still guarded by the queen in row 1 but that
we can place a queen in the second column and now push the location into the stack (Step-4).
When we try to place a queen in row 4, however, we find all positions are guarded. Column 1 is
guarded by the queen in row 1 and the queen in row 3. Column 2 is guarded by the queen in row 2
and the queen in row 3. Column 3 is guarded by the queen in row 3, and column 4 is guarded by both
the queen in row 1 and row 2.
Now, therefore backtrack to the queen in row 3 and try to find another place for the queen
because the queen in row 2 is guarding both column 3 and column 4, there is no option for a queen in
row 3. Once again we backtrack by popping the stack and find that the queen in row 2 has nowhere
else to go, so now backtrack to the queen in row 1 and move the queen to column 2. This position is
shown in the figure below (Step-5).